murrax.dev Recently Edited: Learning with ObsidianObject Capabilities Security ModelGPU Architecture

Rank 1 Constraint System

An [[Arithmetic circuits|arithmetic circuit]] where each equality constraint has exactly one multiplication.

This restriction allows us to use bilinear [[Pairings (Elliptic Curves)]]s.

The output of a pairing G1⋅G2→GTG_1 \cdot G_2 \rightarrow G_T cannot be paired again, since an element in GTG_T cannot be used as input to a pairing. This why we can only have one multiplication.

Our witness is a 1×m1\times m vector containing the values of all the input, intermediate, and output variables. By convention, the first element is always 1 to make some calculations easier.

The intermediate variables are variables we introduce to our arithmetic circuit to satisfy the restriction that we must have exactly one multiplication per equation.

Representation

Oa=La⋅RaOa = La \cdot Ra where O,L,RO, L, R are matrices encoding the output variables, the LHS, and the RHS.

Example

z=xyt=zx\begin{align} z = xy\\ t = zx \end{align}

has witness of form a=[1,z,t,x,y]a=[1, z, t, x, y] and equation of form

[0100000100]a=[0001001000]a⋅[0000100010]\begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \end{bmatrix}a = \begin{bmatrix} 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ \end{bmatrix}a \cdot \begin{bmatrix} 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0\\ \end{bmatrix}

Matrix Size

Our matrix will have mm columns, where mm is the number of variables in the system, +1+1 for the constant column.

It will have nn rows, where nn is the number of constraint equations in the circuit.

References